//
// Created by zuo on 2024/7/7.
// 题目链接 https://www.lanqiao.cn/problems/2489/learning/?page=1&first_category_id=1&problem_id=2489   k -> 10
// 题目链接 https://www.lanqiao.cn/problems/1230/learning/?page=1&first_category_id=1&problem_id=1230   N -> M
//

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAX = 1e5 + 7;
int a[MAX];
char ch[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};

int main()
{
    // // k 进制数 -> 十进制数
    // ll x = 0;   // 别忘了
    // for (int i = 0; i < n; i++)
    // {
    //     x = x * k + a[i];   // 12345 数组里下标为 a[0] = 1 ...
    // }
    // cout << x << '\n';

    // // 十进制数 -> k 进制数
    // ll x;
    // cin >> x;
    // while (x)
    // {
    //     a[cnt++] = x % k;
    //     x /= k;
    // }
    // reverse(a, a + cnt); // 注意要反转一下才能实现  12345 a[0] = 1 的情况

    // // k -> 10
    // string s = "2021ABCD";
    // ll x = 0;
    // for (int i = 0; i < s.length(); i++)
    // {
    //     if ('0' <= s[i] && s[i] <= '9') x = x * 16 + s[i] - '0';
    //     else x = x * 16 + s[i] - 'A' + 10;
    // }
    // cout << x;

    // N -> M  => N -> 10 -> M
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int N, M;
        cin >> N >> M;
        string s;
        cin >> s;
        int len = s.length();
        // 把 string 对应的每一位数转换成 int
        for (int i = 0; i < len; i++)
        {
            if ('0' <= s[i] && s[i] <= '9') a[i] = s[i] - '0';
            else a[i] = s[i] - 'A' + 10;
        }
        // N -> 10
        ll x = 0;
        for (int i = 0; i < len; i++)
        {
            x = x * N + a[i];
        }
        // 10 -> M
        string ans;
        while (x)
        {
            ans += ch[x % M];
            x /= M;
        }
        reverse(ans.begin(), ans.end());
        cout << ans << '\n';
    }

    return 0;
}
